#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char *data;     // 存储数组数据
    int size;       // 当前数组大小
    int capacity;   // 数组的最大容量
} DynamicArray;

// 初始化动态数组
void InitArray(DynamicArray *arr, int initialCapacity) {
    if (arr->data != NULL) {
        printf("Array already initialized.\n");
        return;
    }

    arr->data = (char *)malloc(initialCapacity * sizeof(char));
    if (arr->data == NULL) {
        perror("Failed to initialize array");
        exit(EXIT_FAILURE);
    }
    arr->size = 0;
    arr->capacity = initialCapacity;
}

// 扩展数组容量
void ResizeArray(DynamicArray *arr, int newCapacity) {
    if (newCapacity <= arr->capacity) return;

    // 先尝试分配新内存
    char *new_data = (char *)realloc(arr->data, newCapacity * sizeof(char));
    
    if (new_data == NULL) {
        // realloc 失败，原内存仍然有效
        perror("Failed to resize array");
        // 不更新 arr->data, 继续使用原来的内存
        return;
    }

    // realloc 成功，更新指针
    arr->data = new_data;
    arr->capacity = newCapacity;
}

// 向数组中添加元素
void apppendElement(DynamicArray *arr, char element) {
    if (arr->data == NULL) {
        printf("Array not initialized.\n");
        return;
    }

    // 如果数组满了，扩展容量
    if (arr->size == arr->capacity) {
        ResizeArray(arr, arr->capacity * 2);  // 每次扩展为原来大小的两倍
    }
    arr->data[arr->size] = element;
    arr->size++;
}

// 在指定位置插入元素
void AddElement(DynamicArray *arr, int index, char element) {
    if (arr->data == NULL) {
        printf("Array not initialized.\n");
        return;
    }

    if (index < 0 || index > arr->size) {
        printf("Index out of bounds.\n");
        return;
    }

    // 如果数组满了，扩展容量
    if (arr->size == arr->capacity) {
        ResizeArray(arr, arr->capacity * 2);  // 每次扩展为原来大小的两倍
    }

    // 从后往前移动元素，腾出位置
    for (int i = arr->size; i > index; i--) {
        arr->data[i] = arr->data[i - 1];
    }

    // 插入新元素
    arr->data[index] = element;
    arr->size++;
}

// 删除指定位置的元素
void RemoveElement(DynamicArray *arr, int index) {
    if (arr->data == NULL) {
        printf("Array not initialized.\n");
        return;
    }

    if (index < 0 || index >= arr->size) {
        printf("Index out of bounds.\n");
        return;
    }

    // 从指定位置开始，将后面的元素前移
    for (int i = index; i < arr->size - 1; i++) {
        arr->data[i] = arr->data[i + 1];
    }

    arr->size--;
}

// 释放数组内存
void FreeArray(DynamicArray *arr) {
    if (arr->data == NULL) {
        printf("Array not initialized.\n");
        return;
    }

    free(arr->data);
    arr->data = NULL;
    arr->size = 0;
    arr->capacity = 0;
}

// 打印数组中的所有元素
void PrintArray(DynamicArray *arr) {
    if (arr->data == NULL) {
        printf("Array not initialized.\n");
        return;
    }

    for (int i = 0; i < arr->size; i++) {
        printf("%c ", arr->data[i]);
    }
    printf("\n");
}

int main() {
    DynamicArray arr = {NULL, 0, 0}; // 初始化为空的数组

    // 初始化数组，初始容量为 4
    InitArray(&arr, 4);

    // 向数组中添加元素
    apppendElement(&arr, 'A');
    apppendElement(&arr, 'B');
    apppendElement(&arr, 'C');
    apppendElement(&arr, 'D');
    apppendElement(&arr, 'E');  // 这个操作会导致数组扩展

    // 打印数组
    printf("Array after additions:\n");
    PrintArray(&arr);

    // 在第二个位置插入 'X'
    AddElement(&arr, 1, 'X');
    printf("Array after inserting 'X' at position 1:\n");
    PrintArray(&arr);

    // 删除第三个位置的元素
    RemoveElement(&arr, 2);
    printf("Array after removing element at position 2:\n");
    PrintArray(&arr);

    // 释放数组内存
    FreeArray(&arr);

    return 0;
}
